package l.l.w.leetcode.GenerateParentheses;

import com.sun.javafx.runtime.SystemProperties;

import java.util.LinkedList;
import java.util.List;

/**
 * Created by llw on 2017/11/1.
 */
public class GenerateParentheses {

    public List<String> generateParenthesis(int n) {
        LinkedList<String> result = new LinkedList<>();
        StringBuilder sb = new StringBuilder(n);
        generate(result,sb,1,0,n);
        return result;
    }
    private void generate(List<String> list, StringBuilder sb, int i, int total,int n){
        sb.append('(');
        if(i == n){
            int add = 2 * n - sb.length();
            for(int k = 0; k < add; ++k){
                sb.append(')');
            }
            list.add(sb.toString());
            sb.delete(sb.length()-add-1,sb.length());
            return;
        }

        int dis = i - total;
        for(int j=total; j <= i; ++j){
            generate(list,sb,i+1,total,n);
            sb.append(")");
            total++;
        }
        sb.delete(sb.length()-(dis+1)-1,sb.length());
    }

    public static void main(String[] args) {
        List<String> result = new GenerateParentheses().generateParenthesis(4);
        System.out.println(result);
    }
}
